package avlTree;

public class avlTree {

   static class TreeNode{
public int val;
public int bf;
public TreeNode parent;
public TreeNode left;
public TreeNode right;

       public TreeNode(int val) {
           this.val = val;
       }
   }

   public TreeNode root;

public boolean insert(int val){
    TreeNode node=new TreeNode(val);
    //如果avl树为空，将第一个插入的节点作为根节点
if(root==null){
    root=node;
    return true;
}
TreeNode parent = null;
TreeNode cur=root;
while(cur!=null){
    if(cur.val>val){
        parent=cur;
        cur=cur.left;
    }else if(cur.val==val){
        return false;
    }else {
        parent=cur;
        cur=cur.right;
    }
}
if(parent.val>val){
    parent.left=node;
    node.parent=parent;
}else {
    parent.right=node;
    node.parent=parent;
}
cur=node;

while(parent!=null){
    if(cur==parent.right){
        parent.bf--;
    }else {
        parent.bf++;
    }

    if(parent.bf==0){
        return true;
    }else if(parent.bf==1||parent.bf==-1){
        cur=parent;
        parent=parent.parent;
    }else {
        if(parent.bf==2){
            if(cur.bf==1){
revolveRight(parent);
            }else {
revolveLR(parent);
            }
        }else {
            if(cur.bf==1){
revolveRL(parent);
            }else {
revolveLeft(parent);
            }
        }
        break;
    }
}
return true;
}


    private void revolveLeft(TreeNode parent){
    TreeNode subR=parent.right;
    TreeNode subRL=subR.left;
    if(subRL!=null){
        subRL.parent=parent;
    }
    parent.right=subRL;

    if(parent==root){
        root=subR;
        subR.parent=null;
    }else{
        TreeNode pParent=parent.parent;
        if(pParent.left==parent){
            pParent.left=subR;
        }else {
            pParent.right=subR;
        }
        subR.parent=pParent;
    }

    parent.parent=subR;
    subR.left=parent;

    parent.bf=subR.bf=0;

    }

    private void revolveRL(TreeNode parent){
TreeNode subR=parent.right;
TreeNode subRL=subR.left;
int bf=subRL.bf;
revolveRight(subR);
revolveLeft(parent);

if(bf==-1){
    parent.bf=1;
    subRL.bf=0;
    subR.bf=0;
}else {
    parent.bf=0;
    subR.bf=-1;
    subRL.bf=0;
}
    }

    private void revolveRight(TreeNode parent){
    TreeNode subL=parent.left;
    TreeNode subLR=subL.right;

    if(subLR!=null){
        subLR.parent=parent;
    }
    parent.left=subLR;

    if(parent==root){
        root=subL;
    }else {
        TreeNode pParent=parent.parent;
        if(parent==pParent.right){
            pParent.right=subL;
        }else {
            pParent.left=subL;
        }
        subL.parent=pParent;
    }
    parent.parent=subL;
    subL.right=parent;
    parent.bf=subL.bf=0;
    }
    private void revolveLR(TreeNode parent){
TreeNode subL=parent.left;
TreeNode subLR=subL.right;
int bf=subLR.bf;
revolveLeft(subL);
revolveRight(parent);
if(bf==1){
    parent.bf=-1;
    subL.bf=0;
    subLR.bf=0;
}else {
    parent.bf=0;
    subL.bf=1;
    subLR.bf=0;
}
    }

    public void inOrder(TreeNode root){
    if(root==null)return;
    inOrder(root.left);
        System.out.println(root.val);
    inOrder(root.right);
    }

    private int height(TreeNode root){
    if(root==null)return 0;
    int leftH=height(root.left);
    int rightH=height(root.right);
    return leftH>rightH?leftH+1:rightH+1;
    }

    public boolean isBlanced(TreeNode root){
    if(root==null)return true;
    int leftH=height(root.left);
    int rightH=height(root.right);
    if(leftH-rightH!=root.bf){
        System.out.printf(root.val+":平衡因子异常");
        return false;
    }
    return Math.abs(leftH-rightH)<=1&&isBlanced(root.left)&&isBlanced(root.right);
    }

}
